package sortsuanfa;

public class Solution {
//    public  static int []arr=new int[] {7,6,5,4,9,11,10,33};
    public static void main(String[] args) {
//        int arr[] = maopao();



        int arr[] = new int[]{3,2,6,8,9,10,11};
        quickSort(arr,0,arr.length-1);
        for(int i:arr) {
            System.out.println(i);
        }
    }

    //快拍
    public static void quickSort(int arr[], int left, int right){

        if(left > right){
            return;
        }
        int key = arr[left];
        int l = left ;
        int r =  right ;
        while (l != r) {
            while ( arr[r] >= key && l< r ){
                r--;
            }
            while (arr[l] <= key && l < r){
                l++;
            }

            if(l < r){
                int temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }

        }
        arr[left] = arr[l];
        arr[l] = key;
        quickSort(arr,left,l - 1);
        quickSort(arr,l+1,right);
    }

    public static void sort(int[] array, int left, int right) {
        if(left > right) {
            return;
        }
        // base中存放基准数
        int base = array[left];
        int i = left, j = right;
        while(i != j) {
            // 顺序很重要，先从右边开始往左找，直到找到比base值小的数
            while(array[j] >= base && i < j) {
                j--;
            }

            // 再从左往右边找，直到找到比base值大的数
            while(array[i] <= base && i < j) {
                i++;
            }

            // 上面的循环结束表示找到了位置或者(i>=j)了，交换两个数在数组中的位置
            if(i < j) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }

        // 将基准数放到中间的位置（基准数归位）
        array[left] = array[i];
        array[i] = base;

        // 递归，继续向基准的左右两边执行和上面同样的操作
        // i的索引处为上面已确定好的基准值的位置，无需再处理
        sort(array, left, i - 1);
        sort(array, i + 1, right);
    }

    //归并

    // 冒泡
    public static int[] maopao() {
        int arr[] = {11,22,33,9,7,5};
        for(int i=0; i<arr.length; i++) {
            for (int j=0; j < arr.length -i - 1; j++) {
                if(arr[j] > arr[j+1]) {
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
}
